Parallel computer processing systems are well known and are typically divided into two basic types, single-instruction, multiple-data (SIMD) systems and multiple-instruction, multiple-data (MIMD) systems. SIMD systems use multiple processing elements which are linked together to execute the same instruction on different data points so that the same task is accomplished simultaneously on all of the different data points. A classic example of an SIMD system is an image processing system where multiple processing elements each use the same instructions to simultaneously process different pixel points in an image. MIMD systems also have multiple processing elements which are linked together, but each processing element is executes a different set of instructions on different data values. In this way, a MIMD system can split up different segments of instructions necessary to solve a problem and execute these different segments simultaneously to increase the speed at which the problem is solved.
SIMD systems typically use a central controller to disseminate the single instruction being executed and to coordinate multi-transfer of information among the processing elements. In contrast, MIMD systems use either a shared memory model or message passing model to coordinate the various processing elements and communicate information among them. In the shared memory model, each processing element has access to a common memory used for storing data and control flags which are used to communicate information and coordinate the processing elements. In contrast, each processing element in the message passing model has only its own distributed, local memory and all communication among processing elements occurs via messages passed along a series of connection links between processing elements.
One of the key trade-offs in designing message passing systems for MIMD computer systems is the manner in which processing elements are connected. Obviously, if every processing element is directly and singularly connected to every other processing element, the speed at which messages can be passed is maximized because each message takes only one hop time to move from one processing element to another. The disadvantage with such an all-to-all connection scheme is that, as the number of processing elements increases, the number of connections required grows geometrically and quickly becomes impractical to implement. At the other extreme, if every processing element were connected to one common connection network, such as a single bus, then messages would still take only one hop time to transfer between processing elements, but only one pair of processing elements could communicate with each other at any given time. To solve these connection problems for massively parallel MIMD computer processing systems, having large numbers of message passing processing elements, two general types of connection schemes have been developed: two-dimensional and n-dimensional grid networks.
In a two-dimensional grid network, all of the processing elements or nodes are directly connected in a regular pattern to four other adjacent processing elements (e.g., left, right, up and down), and messages are routed through this message passing network from a sending node to a receiving node by having each node receive messages and, if the message is not for that node, sending the message on to one of the other adjacent nodes. Examples of a two-dimensional grid networks include the Transputer.RTM. systems developed by Inmos Ltd, Bristol, England, as described in U.S. Pat. Nos. 4,692,861, 4,783,734 and 5,243,698 and the massively parallel array processing system developed by Digital Equipment Corp., Maynard, Mass., as described in U.S. Pat. Nos. 4,985,832 and 5,276,895.
In an n-dimensional grid network, all of the processing elements or nodes are directly connected in a regular pattern to six or more other processing elements. In essence, an n-dimensional grid network is similar to a two-dimensional grid network, only the number of dimensions in the network has been increased. Examples of n-dimensional grid networks include the hypercube networks developed by nCUBE Corp., Foster City, Calif., as described in U.S. Pat. Nos. 5,113,523 and 5,367,636, and by Thinking Machines Corp., Cambridge, Mass., as described in U.S. Pat. Nos. 5,152,000 and 5,367,692, as well as the hexagonal mesh network developed by the University of Michigan, as described in U.S. Pat. No. 5,101,480.
A popular programming model for message passing networks is the communication sequential process (CSP) programming model which was originally developed by Prof. C. A. R. Hoare. In the CSP model, a software program is divided into independent processes which can exchange data and synchronize their activity via communication links referred to as channels. Each process represents a segment of the software program that can execute independently and of, and generally concurrently with, other segments of the program. Each channel serves as a communication path by which information and data are exchanged between processes. To insure synchronization of processes, transmissions are always acknowledged by the receiving process and the sending process always waits to receive this acknowledgement. Concurrent processing in the ANSI C programming language, for example, conforms to the CSP programming model.
One of the more difficult problems in managing CSP inter-process communications for a message passing MIMD computer processing systems is preventing deadlocks. Deadlocks are situations where the passing of messages among the various process stops because some or all of the processes are endlessly waiting or blocked. In networks where messages are passed from one node to the next on their way from a source node to a destination node, the messages may be temporarily stored in a buffer of an intermediate node during the message passing process. In this situation, deadlocks can occur because one or more of the intermediate nodes will have only a limited buffer space available for the temporary storage of information passing by that node on its way to another node. If the buffers in adjacent nodes fill up, for example, then no messages can be sent to unload the buffer in the center node and a deadlock situation is created. By analogy, a deadlock is somewhat like a traffic gridlock across a series of traffic intersections where cars in one intersection cannot move forward because there is no room in any of the adjacent intersections.
Two techniques have been used, in an effort to decrease or prevent deadlocks when managing CSP inter-process communications. First, the message passage networks are designed with regular interconnections between nodes. The regularity of the interconnections makes it easier to anticipate deadlock conditions and easier to accommodate deadlock conditions by using information that is known about the structure of the network and contained, for example, within the address of a message to help in preventing deadlock conditions. Second, the routing algorithms used in the message passage networks are usually designed to implement adaptive routing, rather than oblivious routing. Oblivious routing implies that, when a message directed to a destination node B, for example, arrives at an intermediate node A, that message is always routed to intermediate node C, regardless of the "traffic" conditions associated with node C. Adaptive routing, on the other hand, allows intermediate node A to check on the "traffic" conditions at the next intermediate node C, and, if the conditions are not good, select an alternate intermediate node for routing the message to destination node B. An example of an adaptive routing message passing system is shown in U.S. Pat. No. 5,170,393.
While the use of regular interconnections and adaptive routing can effectively handle most deadlock situations in message passing networks that utilize intermediate buffers, the use of these two techniques is not without a performance penalty. Specifically, the requirement for regular interconnections necessarily increases the number of inter-node hops, for example, which must be made to pass a message from one side of a network to another, particularly in a 2-dimensional grid network. The use of adaptive routing necessarily increases the overhead associated with the routing algorithms, and hence decreases the overall message passing performance of the network.
Other attempts have been made to provide interprocessor switching networks that solve the deadlock problem. The use of control circuitry as part of a regularly-structured message passing network is described in U.S. Pat. Nos. 5,058,001, 5,105,424 and 5,291,489. The problem of deadlocks in an irregularly connected MIMD computer processing system is described in U.S. Pat. No. 4,177,514, which proposes a separate, decentralized control network connected from multiple control nodes to multiple processing nodes to solve the deadlock problem. In U.S. Pat. No. 5,347,450, router circuitry in each node for a network switched communication path between a source node and a destination node, thereby eliminating the need for any intermediate buffers in the message passing network. Unfortunately, these types of hardware and control solutions only complicate and limit what is otherwise a very simple inter-process communication architecture for the CSP programming model.
A different attempt to increase the performance of message passing networks is proposed in U.S. Pat. No. 5,247,694. In this patent, a problem graph is created to represent the various processes that comprise a given software program. The problem graph is then used to aid in assigning processes to processing nodes so as to optimize communications among the processing nodes of a regularly connected hypercube network for the given software program. In essence, this solution optimizes the way in which the software program is divided so as to avoid deadlocks when executing that particular program, rather than altering the message passing network so as to prevent the occurrence of deadlocks in the first place.
While existing techniques for providing message passing networks in a MIMD computer processing system offer many advantages over other types of parallel processing computer systems, it would be advantageous to provide a simple message passing system for a MIMD computer processing system which could provide enhanced message passing performance, yet avoid the deadlock problem.